ガベコレ8章 ヒープの分割
ここまでは、全てのオブジェクトは単一のGCに管理される事を仮定していた。しかし、異なる方法で管理する事で性能が上がりうる。
オブジェクトの扱いを年齢により変え、より若いオブジェクトを優先的に回収する。
オブジェクトの管理方法
直接的アリゴリズム
参照カウントのような
間接的アルゴリズム(追跡型アルゴリズム)
オブジェクトを動かすもの
マークコンパクト
コピー
動かさないもの
マークスウィープ
8.1 用語の定義
同じメモリ管理ポリシーの論理的な集合をスペースと呼ぶ。
1つのスペースは複数のチャンクを持つ。
チャンクは連続していたり、2べきサイズ、2べきアライメントである事が多い。
8.2 分割の理由
異なるポリシーや異なるメカニズムで管理すると効率的なことが多い。
様々な分割する動機があるので、それを見ていく。
移動性による分割
移動可能なオブジェクトと移動不可、もしくは移動が重いオブジェクトを区別することがある。
例えば以下のことで移動不能を得る。
ランタイムとコンパイラ間のコミュニケーション不足のため(これ何?)
OSとか(e.g. IOバッファとして)に渡したり
非同期の移動も最適化の邪魔をすることがある。
オブジェクトを移動するには、そのオブジェクトへの全ての参照を更新する必要がある。
対照的にオブジェクトを移動しない回収であれば、追跡コレクタは1つの参照を見つければ十分(なんで突然これがここで主張されている?)。
GCの「外」のライブラリへオブジェクトの参照が渡されると、そのオブジェクトは移動不能となる。
そのようなオブジェクトはピン留めされるもしくは、ライブラリがそれにアクセスできる間はGCが無効となっている必要がある。
直接的な参照をライブラリに渡すかわりに、間接的な参照(ハンドル)を渡すことでこれを回避することができる。
オブジェクトを移動させるために更新しないといけない参照はルート集合も含まれる。
ルート集合の特定は大変。
11章でやる。
よくとられる方法のうち1つは、保守的にスタックとレジスタを走査すること。
これは型情報が無いとできない。
スタック上の値のうちポインタではないとわかるもの(ヒープの外や、より高いスタックを指しているもの)を捨てる。
捨てられなかったものはポインタである。
偶然ポインタに見える数値を変更するとマズいので、保守的に行なうならばこれらのポインタは移動不能である。
しかし準コピーコレクタ(p. 39)ではヒープ中のオブジェクトの適切な情報があれば曖昧なルートから到達可能に見えるオブジェクトを除き移動可能である。 ヒープ上のポインタからのみ指されている(型情報付き)オブジェクトは、適宜ポインタ値を変更して移動できるが、(レジスタなどの)ルートから指されているオブジェクトは動かせない。動かせるものだけ動かす方法を準コピーコレクタという。
サイズによる分割
デカいオブジェクトを移動させるのは、断片化するよりも望ましくない。
よくある戦略として、ある閾値より大きなオブジェクトをラージオブジェクトスペース(LOS)に置く手がある。
しきい値はページサイズの半分でよい。
大きなオブジェクトは1つのページに置かれ、マークスイープのような非移動型コレクタで管理される。
1つのオブジェクトを専用のページに配置することで、「Bakerのトレッドミル」や仮想メモリページの再マッピングにより仮想的にコピーもできるようになる。
スペースのための分割
オブジェクト群の隔離によりヒープの使用量を減らすのに有益であることがある。
空間局所性が高いと嬉しい。
逐次割り付けとフリーリストの割付コストの差は小さい。
しかし、特に年少世代では局所性の良くなる前者のほうが良い。
コピーコレクタとスライディングコレクタは共に断片化せず、逐次割り付けが可能。
しかし、コピーコレクタは2倍の領域が必要で、マークコンパクトは遅い。
よって領域を分けよう。
しばらく生き、断片化が懸念とならないオブジェクトは非移動が主でたまに圧縮する領域に置く。
割付率が高くて死亡率が高いオブジェクトは高速な割付、安価なGCのコピーコレクタにて管理。
GCコストは生存オブジェクト数に比例し、それは多くないという仮定
LOSを非コピー型コレクタで管理するもう1つの理由は、大きいオブジェクトのコピーは重いから
LOSをコピーコレクタで管理すると、LOSの領域が倍かかって辛いということ?
種類による分割
型などの特定の属性をアドレスからわかるようになる。
アドレスの先のフィールドをロードしなくていいので、キャッシュが汚れない。
オブジェクトのヘッダに情報を書かなくても、スペースを見たら属性がわかる。
オブジェクトの種類がわかると嬉しいことがある。
ポインタを含まないオブジェクトは追跡型コレクタで走査しなくて良い。
大きなポインタの配列の処理は移動のコストより追跡コストのほうが高い(そうだね)。
保守的コレクタでは、ポインタっぽく見えやすい(偽りのポインタ)ビットマップデータを走査されないとこに置くと嬉しい。
本質的に循環しないオブジェクトを隔離すると循環も回収できるコレクタの時は嬉しい。
仮想マシンのコードは長生きしがちだから、動かさないようなとこに置いてもよいことがしられている。
回収率のための分割
寿命の統計を利用できる。
これが隔離する最もよく知られた理由。
1976年には「新しく割付られたデータは居座るか短期間のうちに捨てられる可能性が高い」ことが述べられた。
多くのオブジェクトは若くして死ぬ 弱い世代別仮説
オブジェクトの寿命の分布が歪んでいるとヒープの部分集合だけをくりかえしてGCすることには価値がある。
世代別コレクタでは一般にこうする。
デメリットとして以下
ヒープ中に回収されないごみができるので、そうしない時より新しいオブジェクトに使える領域が減るので、コレクタの頻度が上がる。
GCされる領域とされない領域を分けると管理情報を記録するのがより大変になる。
しかし、GCするとこの生存率が低ければ効率的である。
停止時間を減らすための分割
追跡型コレクタのGCコストは追跡される生存オブジェクト数に依存する。
コピーコレクタは生存してるオブジェクト数に依存する。
マークスウィープでは追跡コストが高い。
追跡するスペースを小さくすると、そこにかかる時間は減る。
これはストップザワールド型では停止時間が減ることでもある。
分割による改善は平均停止時間だけ。
十分な領域が取れるまで全体のGCが必要となることがあるので最悪停止時間は減らない。
うまい分割をするのは主にプログラマの責任となる。
MLとかなら自動推論とかもできる。
局所性のための分割
コピーコレクタのコピーのしかたで局所性が改善できたりもすることを4章でやった(親子を近くにおく)。
スレッドによる分割
GCはミューテータとコレクタ間での同期が必要。
オンザフライ型ではミューテータスレッドを全て止めることは無い。
ストップザワールド型でも同期が必要。
一度に止めるスレッドを1つにして、そのスレッドの割り付けたオブジェクトだけを回収するなら同期コストは下がる。
そうするにはスレッドローカルなヒープレットにわりふるのと、スレッド間で共有可能なオブジェクトの区別が必要。
より大きな粒度で、マルチタスクの仮想マシンではタスクローカルなものと共有なものを分けておけば、タスクの終了後前者は低コストで回収できて嬉しい。
可用性(アクセスしやすさ)による分割
オブジェクトへのアクセスコストに合わせて分割する
リモート(の対象の概念を実装したローカル上の)オブジェクトへのアクセスはローカルオブジェクトより桁違いにコストがかかるので、異なるポリシーで管理したほうがいい
NUMAではオブジェクトを近いメモリに置くと良い。
ミュータビリティーによる分割
参照カウントのメモリマネージャは更新のコストが高いので、頻繁に更新されるのには向かない。
ヒープの巨大なオブジェクトは更新が少ないから参照カウントが向いている可能性がある。
追跡型だと舐めるのが大変。
DoligezとGonthierの手法
スレッドローカルなオブジェクトはそれ以外のとこから参照されてはいけない。
こうするとスレッドローカルなヒープを非同期にGCできる。
スペースを跨いだポインタを調べる必要がなくなる。
8.3 どう分割するか
自明な分割として、重なりのないアドレス範囲にヒープを分割する。
最もシンプルな方法として、各スペースを連続するチャンクにとる。
チャンクのアラインメントは2べき境界にすると効率が良い。
どのスペースに属しているかがアドレスの上位ビットを見るとわかるから。
しかし32ビットシステムでは連続領域の確保が難しいかもしれない。
チャンクの不連続な集まりとして実装する手もある。
64ビットシステムではほとんどの場合問題ない
一方スペースを実装するのに、アドレスを隔離しなくても、ヘッダの領域でスペースを表わすという手もある。
利点
非移動型コレクタでも属性による分割ができる
スペースの(論理的)移動が可能となる。
一時的にピン留めする扱いが簡単になる。
実行時に選択するほうが静的にするよりも正確となることがある。
静的解析による選択はスケールしない。
欠点
ライトバリアの仕事が増える。
ポインタの更新するたびに指してる先のオブジェクト(やその推移的閉包)のヘッダをいじる必要がある。
ヒープを部分的に回収するのは不完全となる。
ラウンドロビン等で、全ての部分集合を見てまわるようにしても、複数のスペースにまたがる循環ごみを回収できない。
単純でよく使われてる実装としては、他の方法でダメなら全体を舐めること。
8.4 いつ分割するか
分割の決定は静的 あるいは動的にできる。
いつでもじゃん。
世代による分割が最もよく知られる。
この場合動的に行なわれる。
オブジェクトの年齢が上がると昇格する。
コレクタにより隔離されることもある。
ピン留めされたオブジェクトとされていないオブジェクトで、動かせないオブジェクトと動かせるオブジェクトに論理的に分割される。
アロケータにより決定されることもある。
サイズによりLOSに置くかどうかを決めたり。
スレッドローカルなアロケータは共有すると明示されないとスレッドローカルなヒープレットに置き、明示されると共有領域に置く。
世代システムでは新しいオブジェクトが年齢の高いオブジェクトを指しているとどうせ昇格すると同じ領域に置いたりもする。
型(や別の解析)によりスペースを決定することもある。
コンパイラが静的解析で属性を共有することがわかれたらよりよいコードを吐ける。
世代別は普通新しいオブジェクトをナーサリーに置くけど、静的解析で昇格を知れたら最初から昇格させるコードを吐ける。
ヒープが並列コレクタ(15章)で管理されていたら、実行中にミューテータにより再分割されることもある。
これらの使う色分けはある種のスペース分離である。